#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void printNums(int* nums, int numsSize)
{
	for (int i = 0; i < numsSize; i++)
		printf("%d ", nums[i]);
	printf("\n");
}

void _mergeSort(int* nums, int* temp, int left, int right)
{
	if (left >= right)
		return;
	
	int mid = (right - left) / 2 + left;
	_mergeSort(nums, temp, left, mid);
	_mergeSort(nums, temp, mid + 1, right);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (nums[begin1] <= nums[begin2])
			temp[index++] = nums[begin1++];
		else
			temp[index++] = nums[begin2++];
	}
	while (begin1 <= end1)
		temp[index++] = nums[begin1++];
	while (begin2 <= end2)
		temp[index++] = nums[begin2++];

	memcpy(nums + left, temp + left, sizeof(int) * (right - left + 1));
}


void mergeSort(int* nums, int numsSize)
{
	int* temp = (int*)malloc(sizeof(int) * numsSize);
	if (NULL == temp)
	{
		perror("malloc");
		exit(-1);
	}
	_mergeSort(nums, temp, 0, numsSize - 1);

	free(temp);
}

void mergeSort_NotR(int* nums, int numsSize)
{
	int* temp = (int*)malloc(sizeof(int) * numsSize);
	if (NULL == temp)
	{
		perror("malloc");
		exit(-1);
	}

	for (int gap = 1; gap < numsSize; gap *= 2)
	{
		for (int i = 0; i < numsSize; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			if (end2 >= numsSize)
				end2 = numsSize - 1;

			if (end1 >= numsSize - 1)
				break;

			int index = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (nums[begin1] <= nums[begin2])
					temp[index++] = nums[begin1++];
				else
					temp[index++] = nums[begin2++];
			}
			while (begin1 <= end1)
				temp[index++] = nums[begin1++];
			while (begin2 <= end2)
				temp[index++] = nums[begin2++];

			memcpy(nums + i, temp + i, sizeof(int) * (end2 - i + 1));
		}
	}

	free(temp);
}

void countSort(int* nums, int numsSize)
{
	int min = nums[0];
	int max = nums[0];

	for (int i = 0; i < numsSize; i++)
	{
		if (min > nums[i])
			min = nums[i];
		if (max < nums[i])
			max = nums[i];
	}

	int range = max - min + 1;
	int* temp = (int*)malloc(sizeof(int) * range);
	if (NULL == temp)
	{
		perror("malloc");
		exit(-1);
	}

	memset(temp, 0, sizeof(int) * range);

	for (int i = 0; i < numsSize; i++)
		temp[nums[i] - min]++;

	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (temp[i] > 0)
		{
			nums[index++] = i + min;
			temp[i]--;
		}
	}

}

int main()
{
	int nums[] = { 9, 4, 2, 3, 1, 7, 8, 5, 6, 10, -1};
	int Size = sizeof(nums) / sizeof(int);
	printf("%d\n", Size);

	//mergeSort_NotR(nums, Size);
	countSort(nums, Size);

	printNums(nums, Size);

	return 0;
}
